//给定二叉搜索树（BST）的根节点 root 和一个整数值 val。 
//
// 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [4,2,7,1,3], val = 2
//输出：[2,1,3]
// 
//
// Example 2: 
//
// 
//输入：root = [4,2,7,1,3], val = 5
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 数中节点数在 [1, 5000] 范围内 
// 1 <= Node.val <= 10⁷ 
// root 是二叉搜索树 
// 1 <= val <= 10⁷ 
// 
// Related Topics 树 二叉搜索树 二叉树 👍 274 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution700 {
    /**
     * 这里用栈是多此一举
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node.val == val){
                return node;
            }
            if(node.val > val && node.left != null){
                queue.offer(node.left);
            }
            if (node.val < val && node.right != null) {
                queue.offer(node.right);
            }
        }
        return null;
    }

        /**
         * 该方法利用了二叉搜素树的优点，大大较少了搜索的范围
         * @param root
         * @param val
         * @return
         */
    public TreeNode searchBST1(TreeNode root, int val) {
        if(root == null) return null;
        if(root.val == val) return root;
        if(root.val < val) return searchBST(root.right,val);
        return searchBST(root.left, val);
    }
    /**
     * 该方法只是普通的递归搜索，没有利用二叉搜索树的特点
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST2(TreeNode root, int val) {
        if(root == null) return null;
        if(root.val == val) return root;
        TreeNode result1 = searchBST(root.left,val);
        TreeNode result2 = searchBST(root.right,val);
        if(result1 != null || result2!=null){
            return result1 !=null? result1:result2;
        }
        return null;
    }

    public static void main(String[] args) {
        Integer[] arr1 = {4,2,7,1,3};
        TreeNode root = BinaryTreeFactory.generateBinaryTreeFromArray(arr1);
//        Solution solution = new Solution();
//        TreeNode treeNode = solution.searchBST2(root, 2);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
